import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class num897 {
//    List<Integer> list = new ArrayList<>();
//    public TreeNode increasingBST(TreeNode root) {
//        inorder(root);
//        TreeNode dummyhead = new TreeNode();
//        TreeNode node = dummyhead;
//        for(int i : list) {
//            node.right = new TreeNode(i);
//            node = node.right;
//        }
//        return  dummyhead.right;
//    }
//
//    private void inorder(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        inorder(root.left);
//        list.add(root.val);
//        inorder(root.right);
//    }
    Deque<TreeNode> deque = new LinkedList<>();
    public TreeNode increasingBST(TreeNode root) {
        inorder(root);
        TreeNode node = new TreeNode(deque.poll().val);
        TreeNode cur = node;
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            cur.right = new TreeNode(deque.poll().val);
            cur = cur.right;
        }
        return node;
    }
    private void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        deque.offer(root);
        inorder(root.right);
    }
}
